#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<algorithm>

template<class T>
class Less {
public:
	bool operator()(T& A, T& B) {
		return A < B;
	}

};

template<class T>
class Greater {
public:
	bool operator()(T& A, T& B) {
		return A > B;
	}

};



template<class T,class Container=std::vector<T>, class Compare = Less<T> >
class priority_queue {
public:
	int size() {
		return _con.size();
	}
	bool empty() {
		return _con.empty();
	}

	void adjust_up(int n) {
		int child = n;
	    int father = (n - 1) / 2;
		Compare com;
		while (child >= 0) {
			if (com(_con[father], _con[child])) {
				std::swap(_con[father], _con[child]);
				child = father;
				father = (child - 1) / 2;
			}
			else {	
				break;
			}
		}
	}

	void adjust_down(int n) {
		int father = n;
		int child = father * 2 + 1;
		Compare com;
		while (child < size()) {
			if (child + 1 < size() && com(_con[child ],_con[child+1])) {
				child++;
			}

			if (com(_con[father], _con[child])) {
				std::swap(_con[father], _con[child]);
				father = child;
				child = child * 2 + 1;
			}
			else {
				break;
			}

		}
	}

	void push(const T& val) {
		_con.push_back(val);
		adjust_up(_con.size()-1);
	}

	T& top() {
		return _con[0];
	}

	void pop() {
		std::swap(_con[0], _con[size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}


	T& operator[](size_t n) {
		return _con[n];
	}



private:
	Container _con;
};

